/*
 * Copyright (c) 2001, Swedish Institute of Computer Science.
 * All rights reserved. 
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met: 
 *
 * 1. Redistributions of source code must retain the above copyright 
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in the 
 *    documentation and/or other materials provided with the distribution. 
 *
 * 3. Neither the name of the Institute nor the names of its contributors 
 *    may be used to endorse or promote products derived from this software 
 *    without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND 
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE 
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 
 * SUCH DAMAGE. 
 *
 * This file is part of the lwIP TCP/IP stack.
 * 
 * Author: Adam Dunkels <adam@sics.se>
 *
 * $Id: dlist.c,v 1.5 2001/01/31 10:57:21 adam Exp $
 */

/*-----------------------------------------------------------------------------------*/
/* dlist.c
 *
 * Implements a delta list.
 *
 */
/*-----------------------------------------------------------------------------------*/

#include <stdlib.h>

#include "dlist.h"


struct dlist_item {
  struct dlist_item *next;

  int dvalue;  /* delta value */
  dlist_id id;      /* identification number */
  void *item;
};


struct dlist {
  struct dlist_item *first;
};


static dlist_id id = 0;

/*-----------------------------------------------------------------------------------*/
struct dlist *
dlist_new(void)
{
  struct dlist *dl;

  dl = malloc(sizeof(struct dlist));
  dl->first = NULL;
  return dl;
}
/*-----------------------------------------------------------------------------------*/
int
dlist_is_empty(struct dlist *dl)
{
  return dl->first == NULL;
}
/*-----------------------------------------------------------------------------------*/
unsigned int
dlist_first(struct dlist *dl, void **item)
{
  struct dlist_item *di;
  di = dl->first;
  *item = di->item;
  return di->dvalue;
}
/*-----------------------------------------------------------------------------------*/
dlist_id
dlist_insert(struct dlist *dl, void *item, unsigned int value)
{
  struct dlist_item *di, *ni;
  int acc;

  ni = malloc(sizeof(struct dlist_item));
  ni->next = NULL;
  ni->item = item;
  ni->id = ++id;
  
  acc = 0;
  if(dl->first == NULL) {
    ni->dvalue = value;
    dl->first = ni;
    return ni->id;
  }
  if(value <= dl->first->dvalue) {
    ni->next = dl->first;
    dl->first->dvalue -= value;
    dl->first = ni;
    ni->dvalue = value;
    return ni->id;
  }
  for(di = dl->first; di != NULL; di = di->next) {
    acc += di->dvalue;
    if(value >= acc && di->next == NULL) {
      di->next = ni;
      ni->dvalue = value - acc;
      return ni->id;
    } else if(value >= acc && value <= acc + di->next->dvalue) {
      ni->dvalue = value - acc;
      di->next->dvalue -= value - acc;
      ni->next = di->next;
      di->next = ni;
      return ni->id;
    }
  }
  
  return 0;
}
/*-----------------------------------------------------------------------------------*/
void
dlist_update_first(struct dlist *dl, unsigned int newvalue)
{
  /*  DEBUGF("dlist_update_first: dvalue %u newvalue %u\n",
      dl->first->dvalue, newvalue);*/
  dl->first->dvalue = newvalue;
}
/*-----------------------------------------------------------------------------------*/
void *
dlist_remove(struct dlist *dl, dlist_id id)
{
  struct dlist_item *di, *dh;

  dh = NULL;
  for(di = dl->first; di != NULL; di = di->next) {
    if(di->id == id) {
      if(di->next != NULL) {
	di->next->dvalue += di->dvalue;
      }
      if(dl->first == di) {
	dl->first = di->next;
      }
      if(dh != NULL) {
	dh->next = di->next;
      }
      if(di == dl->first) {
	dl->first = di->next;
      }
      free(di);
      return di->item;
    }
    dh = di;
  }    
  return NULL;
}
/*-----------------------------------------------------------------------------------*/
void *
dlist_remove_first(struct dlist *dl)
{
  struct dlist_item *di;
  if(dl->first == NULL) {
    return NULL;
  }
  di = dl->first;
  dl->first = di->next;
  free(di);
  return di->item;
}
/*-----------------------------------------------------------------------------------*/

